package algorithm;

/**
 * 53. 最大子序和
 * @author Panbo Guo
 * @date 2021/7/31
 */
public class T00053 {

    public static void main(String[] args) {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(new Solution().maxSubArray(arr));
    }

    static class Solution {
        public int maxSubArray(int[] nums) {
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            for (int i = 1; i < dp.length; i++) {
                dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            }
            int max = dp[0];
            for (int i = 1; i < dp.length; i++) {
                if (dp[i] > max)
                    max = dp[i];
            }
            return max;
        }
    }
}
